package day230417;

import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/17 10:18
 * 星际密码
 */
public class Main01 {

    // |1 1| * |1 1| = |2 1| => * |1 1| = |3 2|  => |5 3| => |8 5|
    // |1 0|   |1 0|   |1 1|      |1 0|   |.. ..|
    // f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5 近似斐波那契数列
    // 数据量 n [1, 10000] 先存储前 10000 项
    static int[] fibonacci = new int[10001];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 初始化斐波那契
        fibonacci[1] = 1;
        fibonacci[2] = 2;
        for (int i = 3; i <= 10000; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
            fibonacci[i] %= 10000; // 只保留后四位
        }
        while (scan.hasNext()) {
            int n = scan.nextInt(); // 数据个数
            StringBuilder password = new StringBuilder(); // 用于存储密码
            while (n-- != 0) {
                int number = scan.nextInt();
                String partPassWord = String.format("%04d", fibonacci[number]);
                password.append(partPassWord); // 拼接密码
            }
            System.out.println(password);
        }
        scan.close();
    }
}
